package hw1_3;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class TreeNode implements Comparable<TreeNode> {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

    @Override
    public int compareTo(TreeNode other) {
        return Integer.compare(this.value, other.value);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) {
            values[i] = scanner.nextInt();
        }

        List<Integer> inorderResult = huffmanInorder(values);

        for (int i = 0; i < inorderResult.size(); i++) {
            System.out.print(inorderResult.get(i));
            if (i < inorderResult.size() - 1) {
                System.out.print(" ");
            }
        }
    }

    public static List<Integer> huffmanInorder(int[] values) {
        List<TreeNode> nodes = new ArrayList<>();
        for (int value : values) {
            nodes.add(new TreeNode(value));
        }

        TreeNode root = buildHuffmanTree(nodes);

        List<Integer> inorderResult = new ArrayList<>();
        inorderTraversal(root, inorderResult);

        return inorderResult;
    }

    public static TreeNode buildHuffmanTree(List<TreeNode> nodes) {
        // 使用优先队列来存储节点，并按照节点的值进行排序
        PriorityQueue<TreeNode> queue = new PriorityQueue<>(nodes);

        while (queue.size() > 1) {
            // 取出两个权值最小的节点
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();

            TreeNode internalNode;
            // 创建新的内部节点，如果两个节点的值相等，则选择左子树高度小于等于右子树高度的方式连接
            if (left.value == right.value) {
                if ((left.left == null && right.left == null) || height(left) <= height(right)) {
                    internalNode = new TreeNode(left.value + right.value);
                    internalNode.left = left;
                    internalNode.right = right;
                } else {
                    internalNode = new TreeNode(left.value + right.value);
                    internalNode.left = right;
                    internalNode.right = left;
                }
            } else if (left.value < right.value) {
                internalNode = new TreeNode(left.value + right.value);
                internalNode.left = left;
                internalNode.right = right;
            } else {
                internalNode = new TreeNode(left.value + right.value);
                internalNode.left = right;
                internalNode.right = left;
            }

            queue.offer(internalNode);
        }

        return queue.poll();
    }

    public static void inorderTraversal(TreeNode node, List<Integer> result) {
        // 中序遍历二叉树，将节点值存入结果列表中
        if (node != null) {
            inorderTraversal(node.left, result);
            result.add(node.value);
            inorderTraversal(node.right, result);
        }
    }

    public static int height(TreeNode node) {
        // 计算树的高度
        if (node == null || (node.left == null && node.right == null)) {
            return 0;
        }
        return 1 + Math.max(height(node.left), height(node.right));
    }
}

